/*   The MIT License
 *   
 *   Carina Engine
 *   Copyright (c) 2009 2010 2011 2012 Zdravko Velinov
 *   
 *   Permission is hereby granted, free of charge, to any person obtaining a copy
 *   of this software and associated documentation files (the "Software"), to deal
 *   in the Software without restriction, including without limitation the rights
 *   to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 *   copies of the Software, and to permit persons to whom the Software is
 *   furnished to do so, subject to the following conditions:
 *
 *   The above copyright notice and this permission notice shall be included in
 *   all copies or substantial portions of the Software.
 *
 *   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 *   IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 *   FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 *   AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 *   LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 *   OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 *   THE SOFTWARE.
 */

// WARNING: ad hoc

#include "carina/terrain.hh"
#include "carina/math.hh"
#include "carina/common/exception.hh"
#include "carina/common/global.hh"
#include "carina/filters.hh"

#include <iostream>
#include <limits>
#include <stack>

namespace Carina
{
#undef max

QuadtreeNode::QuadtreeNode()
    :   m_Min(std::numeric_limits<float>::max()),
        m_Max(0),
        m_Size(0),
        m_Position(0, 0, 0)
{
    std::fill(m_Child, m_Child+4, nullptr);
}

QuadtreeNode::QuadtreeNode(float min, float max, Vector2 pos, float s)
    :   m_Min(min),
        m_Max(max),
        m_Size(s),
        m_Position(pos.x(), (min+max)/2, pos.y())
{
    std::fill(m_Child, m_Child+4, nullptr);
}

QuadtreeNode::QuadtreeNode(QuadtreeNode** _children)
    :   m_Min(std::numeric_limits<float>::max()),
        m_Max(0),
        m_Size(2*_children[0]->size())
{
    std::copy(_children, _children+4, m_Child);
    for(unsigned i = 0; i < 4; ++i)
    {
        if(m_Child[i]->m_Max > m_Max)
            m_Max = m_Child[i]->m_Max;
        if(m_Child[i]->m_Min < m_Min)
            m_Min = m_Child[i]->m_Min;
    }
    m_Position.set((m_Child[0]->getPosition().x() + m_Child[1]->getPosition().x())/2,
                   (m_Min+m_Max)/2,
                   (m_Child[0]->getPosition().z() + m_Child[2]->getPosition().z())/2);
}

QuadtreeNode::~QuadtreeNode()
{
    for(unsigned i = 0; i < 4; ++i)
        delete m_Child[i];
}

TerrainPatch::TerrainPatch()
    :   m_Delta(nullptr),
        m_PatchType(0),
        m_Min(std::numeric_limits<float>::max()),
        m_Max(0) {}

void TerrainPatch::build(const RendererPtr& renderer, const DynamicArray<Vector3>& data)
{
    unsigned patch_size = static_cast<unsigned>(sqrt(static_cast<float>(data.size())));
    unsigned dsize = static_cast<unsigned>(log2(patch_size-1));
    m_Delta = new float[dsize];
    m_Delta[0] = 0;

    for(size_t i = 0; i < patch_size*patch_size; ++i)
    {
        if(data[i].y() > m_Max)
            m_Max = data[i].y();
        if(data[i].y() < m_Min)
            m_Min = data[i].y();
    }

    m_Position.set((data[0].x() + data[patch_size-1].x())/2,
                   (m_Max+m_Min)/2,
                   (data[0].z() + data[patch_size*patch_size-1].z())/2);

    float   cdelta;
    unsigned i, j;
    float rem_horiz, rem_vert, rem_diag, cur, next_horiz, next_vert, next_diag;
    for(unsigned n = 0, step = 1; n < dsize; ++n, step *= 2)
    {
        if(n)
            m_Delta[n] = m_Delta[n-1];
        for(i = 0; i < patch_size - 2*step; i += 2*step)
            for(j = 0; j < patch_size - 2 * step; j += 2*step) 
            {
                cur = data[i*patch_size + j].y();
                rem_horiz = data[i*patch_size + j + step].y();
                next_horiz = data[i*patch_size + j + step*2].y();
                
                rem_vert = data[(i+step)*patch_size + j].y();
                next_vert = data[(i+step*2)*patch_size + j].y();

                rem_diag = data[(i+step)*patch_size + j + step].y();
                next_diag = data[(i+step*2)*patch_size + j + step*2].y();

                cdelta = fabs(rem_horiz - (next_horiz + cur) / 2.0f);
                if(cdelta > m_Delta[n])
                    m_Delta[n] = cdelta;
                cdelta = fabs(rem_vert - (next_vert + cur) / 2.0f);
                if(cdelta > m_Delta[n])
                    m_Delta[n] = cdelta;
                cdelta = fabs(rem_diag - (next_diag + cur) / 2.0f);
                if(cdelta > m_Delta[n])
                    m_Delta[n] = cdelta;
                cdelta = fabs(rem_diag - (next_horiz + next_vert) / 2.0f);
                if(cdelta > m_Delta[n])
                    m_Delta[n] = cdelta;
            }
    }

    m_Patch = renderer->createVideoBuffer(CE_VERTEX_BUFFER, sizeof(Vector3)*data.size(), data.get(), CE_STATIC_DRAW);
}

TerrainPatch::~TerrainPatch()
{
    delete[] m_Delta;
}

void TerrainPatch::draw(Terrain& terrain)
{
    assert(m_PatchType <= ((unsigned)log2(terrain.getPatchSize()-1) << 4));
    RendererPtr renderer = terrain.getRenderer();
    renderer->setVideoBuffer(m_Patch, sizeof(Vector3), 0);
    renderer->setIndexBuffer(terrain.getIndicesBuffer(m_PatchType), IT_USHORT, 0);
    renderer->drawIndexed(CE_TRIANGLE_LIST, 0, terrain.getIndicesSize(m_PatchType));
}

Terrain::Terrain()
    :   m_Quadtree(nullptr) {}

Terrain::Terrain(const CameraPtr& cam, const ResourceManagerPtr& res_mgr, const string& map_file, const string& splatting)
    :   m_Quadtree(nullptr)
{
    this->init(cam, res_mgr, map_file, splatting);
}

// TODO: config file
void Terrain::init(const CameraPtr& cam, const ResourceManagerPtr& res_mgr, const string& map_file, const string& splatting)
{
    m_Renderer = res_mgr->getRenderer();
    m_State = m_Renderer->createStateObject(MiscStateDescription(CE_FILL_SOLID, CE_CULL_BACK, 0.0f, 0.0f, true, false, false, false));
    m_TileGeomSize = 4.0f;
    m_PatchSize = 17;
    m_TexOffset = 0.5f;
    m_DeltaThreshold = 50;
    m_MaxHeight = 128.0f;
    m_Camera = cam;
    m_LastCamPos = m_Camera->getPosition();
    m_Alphamap = res_mgr->getTexture(splatting);
    m_Tau = 2;
    m_ShaderProg = res_mgr->getShaderProgram("terrain");

    m_Textures[0] = res_mgr->getTexture("dirt.png");
    m_Textures[1] = res_mgr->getTexture("grass.png");
    m_Textures[2] = res_mgr->getTexture("cobblestone.png");

    ImagePtr heightmap = res_mgr->getImage(map_file);
    if(!heightmap)
        THROW_EXCEPTION("cannot load terrain heightmap");
    if(heightmap->format() != VT_R8_UNORM)
        THROW_EXCEPTION("invalid format");

    size_t  height = heightmap->height(),
            width = heightmap->width();

    if(is_not_pow_2_1(height) ||
       (height - 1) % (m_PatchSize - 1) ||
       height <= 5 ||
       height != width)
        THROW_EXCEPTION("Invalid map. The map has to be w = h = 2^n + 1 and bigger than 5x5.");
    if(is_not_pow_2_1(m_PatchSize) || m_PatchSize < 5)
        THROW_EXCEPTION("invalid patch size");

    m_MapSize = height;

    DynamicArray<float> heightmap_float(m_MapSize*m_MapSize);
    for(size_t i = 0; i < m_MapSize*m_MapSize; ++i)
        heightmap_float[i] = reinterpret_cast<const unsigned char*>(heightmap->getData())[i] / 256.0f;

    generateNormalmap(heightmap_float);
    generateTerrainData(heightmap_float);
    generateIndices();
    recalculateDelta();

    m_Renderer->useShaderProgram(m_ShaderProg);
    m_ShaderProg->getVariable("tile_tex_size")->set(m_TexOffset / m_TileGeomSize);
    m_ShaderProg->getVariable("terra_scale")->set(m_TileGeomSize * m_MapSize);

    InputElementArray layout_arr;
    layout_arr.push_back(InputElement("POSITION", VT_RGB32F, 0));
    m_Layout = m_Renderer->createInputLayout(m_ShaderProg, layout_arr);
}

void Terrain::generateNormalmap(const DynamicArray<float>& heightmap)
{
    DynamicArray<Vector4> normalmap(m_MapSize*m_MapSize, Vector4(0.0f, 1.0f, 0.0f, 1.0f));
    DynamicArray<Vector4> normalmap_scaled((m_MapSize-1)*(m_MapSize-1));
    sobel_filter(heightmap.get(), normalmap.get(), m_MapSize, m_MapSize);

    float px, py;
    for(size_t i = 0; i < m_MapSize-1; ++i)
        for(size_t j = 0; j < m_MapSize-1; ++j)
        {
            px = (float)j/(m_MapSize-1);
            py = (float)i/(m_MapSize-1);
            normalmap_scaled[i*(m_MapSize-1) + j] = bilinear_filter(px, py, normalmap.get(), m_MapSize, m_MapSize);
        }

    m_Normalmap = m_Renderer->createTexture(TextureDescription(m_MapSize-1, m_MapSize-1, 1, VT_RGBA32F), normalmap_scaled.get(), 0);
}

void Terrain::generateTerrainData(const DynamicArray<float>& heightmap)
{
    size_t i, j, k, w, n, row;

    size_t patches = m_PatchesCount = (m_MapSize- 1)/(m_PatchSize - 1);
    size_t patches2 = patches*patches;
    m_Patches.resize(patches2);

    /* Creates the terrain patches */
    DynamicArray<Vector3> patch;
    patch.resize(m_PatchSize*m_PatchSize);

    size_t patch_idx, map_idx;
    float beginning = - ((m_MapSize-1)*m_TileGeomSize)/2;
    for(i = 0, n = 0; i < m_MapSize - 1; i += m_PatchSize - 1)
        for(j = 0; j < m_MapSize - 1; j += m_PatchSize - 1, ++n)
        {
            for(k = 0; k < m_PatchSize; ++k)
                for(w = 0; w < m_PatchSize; ++w)        
                {
                    patch_idx = k*m_PatchSize + w;
                    map_idx = (k + i)*m_MapSize + w + j;

                    Vector3& pos = patch[patch_idx];
                    pos.set(beginning + (w + j)*m_TileGeomSize,
                            heightmap[map_idx]*m_MaxHeight,
                            beginning + (k + i)*m_TileGeomSize);
                }
            m_Patches[n].build(m_Renderer, patch);
        }

    /* Builds the quadtree */
    DynamicArray<QuadtreeNode*> children,
                                parents;
    children.resize(patches2, 0);
    parents.resize(patches2 / 4, 0);

    /* Rearranges the patches */
    float node_size = (m_TileGeomSize*(m_PatchSize - 1))/2;
    for(i = 0, j = 0, row = patches; row < patches2; i += patches, row += 2*patches)
        for(; i < row; i += 2) {

            children[j++] = new QuadtreeNode(m_Patches[i].getMin(), m_Patches[i].getMax(), Vector2(m_Patches[i].getPosition()), node_size);
            children[j++] = new QuadtreeNode(m_Patches[i+1].getMin(), m_Patches[i+1].getMax(), Vector2(m_Patches[i+1].getPosition()), node_size);
            children[j++] = new QuadtreeNode(m_Patches[i+patches].getMin(), m_Patches[i+patches].getMax(), Vector2(m_Patches[i+patches].getPosition()), node_size);
            children[j++] = new QuadtreeNode(m_Patches[i+patches+1].getMin(), m_Patches[i+patches+1].getMax(), Vector2(m_Patches[i+patches+1].getPosition()), node_size);
        }

    patches *= 2;
    for(; patches2 > 4; patches /= 2, patches2 /= 4, node_size *= 2)
    {
        for(i = 0, j = 0, row = patches; row < patches2; i += patches, row += 2*patches)
            for(; i < row; i += 8)
            {
                parents[j++] = new QuadtreeNode(children.get()+i);
                parents[j++] = new QuadtreeNode(children.get()+i+4);
                parents[j++] = new QuadtreeNode(children.get()+i+patches);
                parents[j++] = new QuadtreeNode(children.get()+i+patches+4);
            }
        children.swap(parents);
    }

    m_Quadtree = new QuadtreeNode(children.get());
}

void Terrain::generateIndices()
{
    /* Indices generator */
    size_t step, p, k, q, n, i, j;
    size_t isize = m_PatchSize - 1;
    isize *= 6*(isize+1);
    DynamicArray<unsigned short> indices_data;
    indices_data.resize(isize);
    size_t misize = static_cast<size_t>(log2(m_PatchSize-1))*16 + 1;
    m_IndicesBuffer.resize(misize);
    m_IndicesSize.resize(misize);

    for(step = 1, p = 0; step < m_PatchSize-1; step *= 2) {
        struct {
            int      hstep,                                 vstep,                                  end;
        } info[4] = {{static_cast<int>(step),               static_cast<int>(step*m_PatchSize),     static_cast<int>(m_PatchSize - 1)},
                     {static_cast<int>(step*m_PatchSize),   -static_cast<int>(step),                static_cast<int>(m_PatchSize*m_PatchSize - 1)},
                     {-static_cast<int>(step),              -static_cast<int>(step*m_PatchSize),    static_cast<int>(m_PatchSize*(m_PatchSize-1))},
                     {-static_cast<int>(step*m_PatchSize),  static_cast<int>(step),                 0}};
        for(k = 0; k < 16; ++k, ++p) {
            for(q = 0, n = 0, i = 0; q < 4; ++q) {
                if(k & (1 << q)) {
                    indices_data[n++] = i;
                    indices_data[n++] = i + info[q].vstep + info[q].hstep;
                    indices_data[n++] = i += 2*info[q].hstep;
                    while(i != (size_t)info[q].end) {
                        indices_data[n++] = i;
                        indices_data[n++] = i + info[q].vstep - info[q].hstep;
                        indices_data[n++] = i + info[q].vstep;

                        indices_data[n++] = i;
                        indices_data[n++] = i + info[q].vstep;
                        indices_data[n++] = i + info[q].vstep + info[q].hstep;

                        indices_data[n++] = i;
                        indices_data[n++] = i + info[q].vstep + info[q].hstep;
                        indices_data[n++] = i += 2*info[q].hstep;
                        assert(n < isize);
                    }
                }
                else {
                    indices_data[n++] = i;
                    indices_data[n++] = i + info[q].vstep + info[q].hstep;
                    indices_data[n++] = i + info[q].hstep;

                    indices_data[n++] = i + info[q].hstep;
                    indices_data[n++] = i + info[q].vstep + info[q].hstep;
                    indices_data[n++] = i += 2*info[q].hstep;
                    while(i != (size_t)info[q].end) {
                        indices_data[n++] = i;
                        indices_data[n++] = i + info[q].vstep - info[q].hstep;
                        indices_data[n++] = i + info[q].vstep;

                        indices_data[n++] = i;
                        indices_data[n++] = i + info[q].vstep;
                        indices_data[n++] = i + info[q].vstep + info[q].hstep;

                        indices_data[n++] = i;
                        indices_data[n++] = i + info[q].vstep + info[q].hstep;
                        indices_data[n++] = i + info[q].hstep;

                        indices_data[n++] = i + info[q].hstep;
                        indices_data[n++] = i + info[q].vstep + info[q].hstep;
                        indices_data[n++] = i += 2*info[q].hstep;
                        assert(n < isize);
                    }
                }
            }

            for(i = step; i < m_PatchSize-2*step; i += step) {
                for(j = 2*step; j < m_PatchSize-step; j += step) {
                    indices_data[n++] = i*m_PatchSize + j - step;
                    indices_data[n++] = (i+step)*m_PatchSize + j - step;
                    indices_data[n++] = i*m_PatchSize + j;

                    indices_data[n++] = i*m_PatchSize + j;
                    indices_data[n++] = (i+step)*m_PatchSize + j - step;
                    indices_data[n++] = (i+step)*m_PatchSize + j;
                    assert(n < isize);
                }
            }

            m_IndicesSize[p] = n;
            m_IndicesBuffer[p] = m_Renderer->createVideoBuffer(CE_INDEX_BUFFER, n*sizeof(unsigned short), indices_data.get(), CE_STATIC_DRAW);
        }
    }

    indices_data[0] = 0;
    indices_data[1] = (m_PatchSize-1)*m_PatchSize;
    indices_data[2] = m_PatchSize - 1;
    indices_data[3] = (m_PatchSize-1)*m_PatchSize;
    indices_data[4] = m_PatchSize*m_PatchSize - 1;
    indices_data[5] = m_PatchSize - 1;
    m_IndicesSize[p] = 6;

    m_IndicesBuffer[p] = m_Renderer->createVideoBuffer(CE_INDEX_BUFFER, 6*sizeof(unsigned short), indices_data.get(), CE_STATIC_DRAW);

    assert(++p == misize);
}

Terrain::~Terrain()
{
    delete m_Quadtree;
}

void Terrain::recalculateDelta()
{
    unsigned i, j, k, det1, det2, detmin, diff;
    unsigned max_levels = static_cast<unsigned>(log2(m_PatchSize-1));

    float theta = (m_Camera->getProjectionMatrix()[1][1] * m_Camera->getHeight()) / (2 * m_Tau);
    float d = (m_LastCamPos - m_Patches[0].getPosition()).length() / theta;
    for(k = 0; k < max_levels; ++k)
        if(m_Patches[0].getDelta(k) > d)
            break;
    m_Patches[0].setDetail(k);

    for(i = 1; i < m_PatchesCount; ++i)
    {
        TerrainPatch& cur = m_Patches[i*m_PatchesCount];
        TerrainPatch& prev = m_Patches[(i-1)*m_PatchesCount];
        d = (m_LastCamPos - cur.getPosition()).length() / theta;
        det1 = prev.getDetail();
        if(det1 && cur.getDelta(det1-1) > d) {
            cur.setDetail(det1-1);
            cur.stitching(TOP_STITCHING);
        }
        else if(cur.getDelta(det1) > d || det1 == max_levels)
            cur.setDetail(det1);
        else {
            cur.setDetail(det1+1);
            prev.stitching(BOTTOM_STITCHING);
        }
    }

    for(j = 1; j < m_PatchesCount; ++j)
    {
        TerrainPatch& cur = m_Patches[j];
        TerrainPatch& prev = m_Patches[j-1];
        d = (m_LastCamPos - cur.getPosition()).length() / theta;
        det2 = prev.getDetail();
        if(det2 && cur.getDelta(det2-1) > d) {
            cur.setDetail(det2-1);
            cur.stitching(LEFT_STITCHING);
        }
        else if(cur.getDelta(det2) > d || det2 == max_levels)
            cur.setDetail(det2);
        else {
            cur.setDetail(det2+1);
            prev.stitching(RIGHT_STITCHING);
        }
    }

    for(i = 1; i < m_PatchesCount; ++i) {
        for(j = 1; j < m_PatchesCount; ++j)
        {
            TerrainPatch& cur = m_Patches[i*m_PatchesCount + j];
            TerrainPatch& top = m_Patches[(i-1)*m_PatchesCount + j];
            TerrainPatch& left = m_Patches[i*m_PatchesCount + j - 1];
            d = (m_LastCamPos - cur.getPosition()).length() / theta;

            det1 = top.getDetail();
            det2 = left.getDetail();
            diff = abs((int)(det1 - det2));
            assert(diff < 3);
            if(diff == 2) {
                cur.setDetail((det1 + det2)/2);
                if(det1 < det2) {
                    cur.stitching(LEFT_STITCHING);
                    top.stitching(BOTTOM_STITCHING);
                }
                else {
                    cur.stitching(TOP_STITCHING);
                    left.stitching(RIGHT_STITCHING);
                }
            }
            else if(diff) {
                detmin = det1 < det2 ? det1 : det2;
                if(cur.getDelta(detmin) > d) {
                    cur.setDetail(detmin);
                    if(det1 > detmin)
                        cur.stitching(TOP_STITCHING);
                    else
                        cur.stitching(LEFT_STITCHING);
                }
                else {
                    cur.setDetail(detmin+1);
                    if(det1 == detmin)
                        top.stitching(BOTTOM_STITCHING);
                    else
                        left.stitching(RIGHT_STITCHING);
                }
            }
            else
            {
                if(det1 && cur.getDelta(det1-1) > d) {
                    cur.setDetail(det1-1);
                    cur.stitching(TOP_STITCHING | LEFT_STITCHING);
                }
                else if(cur.getDelta(det1) > d || det1 == max_levels)
                    cur.setDetail(det1);
                else {
                    cur.setDetail(det1+1);
                    top.stitching(BOTTOM_STITCHING);
                    left.stitching(RIGHT_STITCHING);
                }
            }
        }
    }
}

void Terrain::setCamera(const CameraPtr& cam)
{
    m_Camera = cam;
    m_LastCamPos = m_Camera->getPosition();
    recalculateDelta();
}

void Terrain::draw(Scene& scene, const Matrix4& transform)
{
    Vector3 cam_pos = m_Camera->getPosition();

    if((m_LastCamPos - cam_pos).length() > m_DeltaThreshold)
    {
        m_LastCamPos = cam_pos;
        recalculateDelta();
    }

    m_Renderer->setStateObject(m_State);

    m_Renderer->useShaderProgram(m_ShaderProg);
    m_Renderer->setInputLayout(m_Layout);
    m_ShaderProg->getTexture("textures")->set(m_Textures, 3);
    m_ShaderProg->getTexture("alphamap")->set(m_Alphamap);
    m_ShaderProg->getTexture("normalmap")->set(m_Normalmap);
    m_ShaderProg->getVariable("sys_TransformMatrix")->set(m_Camera->getTransformMatrix()*transform);

    float r;
    size_t i, x, y;
    const Vector4* const frustum =  m_Camera->getFrustum();
    QuadtreeNode* cur_node;
    Vector3 position;
    float patch_geom_size = m_TileGeomSize*(m_PatchSize - 1),
          map_half_geom_size = m_Quadtree->size();

    std::stack<QuadtreeNode*> node_stack;
    node_stack.push(m_Quadtree);
    while(node_stack.size())
    {
        cur_node = node_stack.top();
        position = transform*cur_node->getPosition();
        node_stack.pop();
        for(i = 0; i < 6; ++i) {
            r = frustum[i].dot(position) + cur_node->size()*(fabs(frustum[i].x()) + fabs(frustum[i].z())) + 2*cur_node->getAverage()*fabs(frustum[i].y());
            if(r < 0)
                break;
        }

        if(i == 6)
        {
            if(cur_node->getChild(0))
            {
                node_stack.push(cur_node->getChild(0));
                node_stack.push(cur_node->getChild(1));
                node_stack.push(cur_node->getChild(2));
                node_stack.push(cur_node->getChild(3));
            }
            else
            {
                x = static_cast<size_t>(floor((position.x() + map_half_geom_size)/patch_geom_size));
                y = static_cast<size_t>(floor((position.z() + map_half_geom_size)/patch_geom_size));
                m_Patches[y*m_PatchesCount + x].draw(*this);
            }
        }
    }
}
}
